/*
 * vim:foldmethod=marker:
 */
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

struct ll_node {
	int data;
	struct ll_node *prev, *next;
};

/* {{{ Mergesort_llist */
/* {{{ print_llist */
void
print_llist(struct ll_node *head)
{
	if (head)
		fprintf(stderr, "%d", head->data);
	head = head->next;
	while (head) {
		fprintf(stderr, " → %d", head->data);
		head = head->next;
	}
	fputc('\n', stderr);
}
/* }}} */

void
Mergesort_llist(struct ll_node *head)
{
	struct ll_node *end, *mid;
	struct ll_node *sorted, *first, *second;
	int t1;
	struct ll_node *t2;

	if (head == NULL || head->next == NULL) /* lengths 0, 1 */
		return;

	end = mid = head;
	while (end && end->next && end->next->next) {
		end = end->next->next;
		mid = mid->next;
	}
	if (end && end->next) {
		end = end->next;
		mid = mid->next;
	}

	mid->prev->next = NULL;
	mid->prev = NULL;
	Mergesort_llist(head);
	Mergesort_llist(mid);

#ifdef D
	fprintf(stderr, "head: ");
	print_llist(head);
	fprintf(stderr, "mid : ");
	print_llist(mid);
#endif

	/*
	 * so we want 'head' to still point to the beginning
	 * of our sorted list
	 * also we don't want any malloc/free shenanigans involved
	 */
	if (head->data > mid->data) { /* this is the tricky part */
		/* {{{ */
#define SWAP(a, b, c) \
	do {\
	    c = a;\
	    a = b;\
	    b = c;\
	} while (0)
		if (head->next && mid->next)
			SWAP(head->next->prev, mid->next->prev, t2);
		SWAP(head->data, mid->data, t1);
		SWAP(head->prev, mid->prev, t2);
		SWAP(head->next, mid->next, t2);
#undef SWAP
		/* }}} */
	}

	/*
	 * from now on only ->prev and ->next pointer should suffice us
	 */
	first = head->next;
	if (first) first->prev = NULL;
	second = mid;

	sorted = head;
	sorted->next = NULL;
	assert(sorted->prev == NULL);

	while (first && second) {
		assert(sorted->next == NULL);

		/* TODO: un-copypaste this code (use 'swap' ptr) */
		if (first->data < second->data) {
			assert(first->prev == NULL);

			sorted->next = first;
			first->prev = sorted;
			sorted = first;

			first = first->next;
			if (first) {
				assert(first->prev == sorted); /* can never be too cautious */
				first->prev->next = NULL;
				first->prev = NULL;
			}
		} else {
			assert(second->prev == NULL);

			sorted->next = second;
			second->prev = sorted;
			sorted = second;

			second = second->next;
			if (second) {
				assert(second->prev == sorted); /* can never be too cautious */
				second->prev->next = NULL;
				second->prev = NULL;
			}
		}
	}
	assert(sorted->next == NULL);
	if (first) {
		assert(first->prev == NULL);
		sorted->next = first;
		first->prev = sorted;
	}
	if (second) {
		assert(second->prev == NULL);
		sorted->next = second;
		second->prev = sorted;
	}
	/*
	 * lists are now connected again
	 *
	 * 'sorted' and either of 'first' and 'second' are now of no use
	 * which is totally ok because we're done here anyway
	 */
#ifdef D
	fprintf(stderr, "head (sorted): ");
	print_llist(head);
#endif

	return;
}
/* }}} */

int
main(int argc, char **argv)
{
	int n;
	struct ll_node *head, *ptr;

	scanf("%d", &n);
	head = ptr = malloc(sizeof *head);
	ptr->prev = NULL;
	while (scanf("%d", &ptr->data) == 1) {
		ptr->next = malloc(sizeof *ptr);
		ptr->next->prev = ptr;
		ptr = ptr->next;
	}

	ptr->prev->next = NULL;
	free(ptr);

	Mergesort_llist(head);

	while (head) {
		printf("%d ", head->data);
		ptr = head;
		head = head->next;
		free(ptr);
	}
	fputc('\n', stdout);

	return 0;
}
